Modern processing devices such as computers, servers, mobile telephones, and storage devices are often required to perform various types of data transformation. For example, data compression is a fundamental operation in a wide variety of communication and storage systems. As is well known, data compression techniques may be lossless or lossy, and may be linear or non-linear.
Examples of lossless data compression techniques include Lempel-Ziv (LZ) compression algorithms such as LZ77 and LZ78, described in J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, 23(3), pp. 337-343, May 1977, and J. Ziv and A. Lempel, “Compression of Individual Sequences via Variable-Rate Coding,” IEEE Transactions on Information Theory, 24(5), pp. 530-536, September 1978, respectively. Another example is the Burrows-Wheeler transform, described in M. Burrows and D. Wheeler, “A block sorting lossless data compression algorithm,” Technical Report 124, Digital Equipment Corporation, 1994.
Lossy data compression techniques are generally data specific, and include, for example, perceptual audio coding (PAC) or MP3 algorithms for audio data, JPEG algorithms for image data, and MPEG algorithms for video data.
These and many other commonly-used data compression techniques are non-linear, which can create a problem in that subsequent signal processing operations performed on decompressed data are very often linear operations. As a result, data compressed using non-linear compression usually must be decompressed to recover the original data before being subject to linear signal processing operations. Typically, most signal processing operations are computation and power intensive, and therefore any reduction in the amount of data subject to signal processing will help reduce both signal processing complexity and the associated power dissipation.
Accordingly, a need exists for an improved lossless, linear data compression technique that can allow compressed data to be subject to linear signal processing operations. Such an arrangement could significantly reduce the complexity of signal processing operations while providing additional benefits in the form of reduced power dissipation, improved signal integrity and better bandwidth utilization.